// bfs 解决最短路问题
// 经典问题 - 边权为 1 的最短路问题，bfs 搜索目标坐标，返回搜索的步数
// 经典问题 - 基因序列变化，字符串每次改变一个字符，变化成最终的基因的最少次数。
// bfs 搜索所有可能变化情况，搜到有效变化，有效次数 + 1

// 例题 3：
// 字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
//
//        每一对相邻的单词只差一个字母。
//        对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
//        sk == endWord
//        给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
//
//
//        示例 1：
//
//        输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
//        输出：5
//        解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
//        示例 2：
//
//        输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
//        输出：0
//        解释：endWord "cog" 不在字典中，所以无法进行转换。
//
//
//        提示：
//
//        1 <= beginWord.length <= 10
//        endWord.length == beginWord.length
//        1 <= wordList.length <= 5000
//        wordList[i].length == beginWord.length
//        beginWord、endWord 和 wordList[i] 由小写英文字母组成
//        beginWord != endWord
//        wordList 中的所有字符串 互不相同

// 解题思路：
// 与例题 2 完全相同，但是需要注意的是，如果直接用判断 List<String> 中是否存在字符串时，可能会导致超时
// 最好是用哈希表判断，因为 List<String> 判断是否存在的时间复杂度是 O(n),而哈希表是 O(1)

import java.util.*;

public class LadderLength {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> hash = new HashSet<>();
        for(String s : wordList) hash.add(s);
        if(!hash.contains(endWord)) return 0;
        int n = beginWord.length();
        Set<String> check = new HashSet<>();
        check.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int ret = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            ret++;
            for(int i = 0; i < size; i++){
                String s = queue.poll();
                for(int j = 0; j < n; j++){
                    char[] sArr = s.toCharArray();
                    for(char k = 'a'; k <= 'z'; k++){
                        sArr[j] = k;
                        String tmp = new String(sArr);
                        if(hash.contains(tmp) && !check.contains(tmp)){
                            if(tmp.equals(endWord)) return ret;
                            queue.offer(tmp);
                            check.add(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
